// 在给定的网格中，每个单元格可以有以下三个值之一：

// 值 0 代表空单元格；
// 值 1 代表新鲜橘子；
// 值 2 代表腐烂的橘子。
// 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

// 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

//  

// 示例 1：



// 输入：[[2,1,1],[1,1,0],[0,1,1]]
// 输出：4
// 示例 2：

// 输入：[[2,1,1],[0,1,1],[1,0,1]]
// 输出：-1
// 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
// 示例 3：

// 输入：[[0,2]]
// 输出：0
// 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
//  

// 提示：

// 1 <= grid.length <= 10
// 1 <= grid[0].length <= 10
// grid[i][j] 仅为 0、1 或 2

#include <vector>
#include <queue>
#include <memory>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        bx = grid.size();
        by = grid[0].size();
        
        queue<shared_ptr<Node>> que{};
        
        int cnt = 0; // 新鲜橘子数量
        for (int i = 0; i < bx; ++i) {
            for (int j = 0;j < by; ++j) {
                if (grid[i][j] == 2) {
                    que.push(make_shared<Node>(i, j, 0));
                } else if(grid[i][j] == 1) cnt += 1;
            }
        }
        if (cnt == 0) return 0;
        int res{}; // 结果/时间
        while (que.size()) {
            auto now = que.front();
            que.pop();
            res = now->mins;
            for(int i = 0;i < 4;++i) {
                int nx = now->x + dir[i][0];
                int ny = now->y + dir[i][1];
                if(nx < 0 || nx >= bx || ny < 0 || ny >= by || grid[nx][ny] != 1)
                    continue;
                grid[nx][ny] = 2;
                cnt -= 1;
                que.push(make_shared<Node>(nx, ny, now->mins+1));
            }
        }
        return cnt <= 0 ? res : -1;
    }
private:
    struct Node{
        int x, y;
        int mins;
        Node(int _x, int _y, int _m):x(_x),y(_y),mins(_m){}
    };
    int dir[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};
    int bx, by;
};

